#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int minFallingPathSum(vector<vector<int>>& matrix) {



	int n = matrix.size();
	
	vector<vector<int>>dp(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		dp[0][i] = matrix[0][i];
	}
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < n; j++) {
			
			if (j == 0) {
				dp[i][j] = min(dp[i - 1][j], dp[i - 1][j + 1]) + matrix[i][j];
				continue;
			}
			if (j < n - 1) {
				int curmin = dp[i - 1][j - 1];
				if (dp[i - 1][j] < curmin) curmin = dp[i - 1][j];
				if (dp[i - 1][j + 1] < curmin) curmin = dp[i - 1][j + 1];
				dp[i][j] = curmin + matrix[i][j];
				continue;
			}
			dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + matrix[i][j];
		}
	}
	int minRes = dp[n - 1][0];
	for (int i = 1; i < n; i++) {
		if (minRes > dp[n - 1][i]) minRes = dp[n - 1][i];
	}
	return minRes;


	
}


